//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005-2014 Simon Howard
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// DESCRIPTION:
//  LineOfSight/Visibility checks, uses REJECT Lookup Table.
//



#include "doomdef.h"

#include "i_system.h"
#include "p_local.h"

// State.
#include "r_state.h"

//
// P_CheckSight
//
fixed_t     sightzstart;        // eye z of looker
fixed_t     topslope;
fixed_t     bottomslope;        // slopes to top and bottom of target

divline_t   strace;         // from t1 to t2
fixed_t     t2x;
fixed_t     t2y;

int     sightcounts[2];


//
// P_DivlineSide
// Returns side 0 (front), 1 (back), or 2 (on).
//
int
P_DivlineSide
( fixed_t   x,
  fixed_t   y,
  divline_t*    node )
{
    fixed_t dx;
    fixed_t dy;
    fixed_t left;
    fixed_t right;

    if (!node->dx)
    {
    if (x==node->x)
        return 2;

    if (x <= node->x)
        return node->dy > 0;

    return node->dy < 0;
    }

    if (!node->dy)
    {
    if (x==node->y)
        return 2;

    if (y <= node->y)
        return node->dx < 0;

    return node->dx > 0;
    }

    dx = (x - node->x);
    dy = (y - node->y);

    left =  (node->dy>>FRACBITS) * (dx>>FRACBITS);
    right = (dy>>FRACBITS) * (node->dx>>FRACBITS);

    if (right < left)
    return 0;   // front side

    if (left == right)
    return 2;
    return 1;       // back side
}


//
// P_InterceptVector2
// Returns the fractional intercept point
// along the first divline.
// This is only called by the addthings and addlines traversers.
//
fixed_t
P_InterceptVector2
( divline_t*    v2,
  divline_t*    v1 )
{
    fixed_t frac;
    fixed_t num;
    fixed_t den;

    den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);

    if (den == 0)
    return 0;
    //  I_Error ("P_InterceptVector: parallel");

    num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
    FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
    frac = FixedDiv (num , den);

    return frac;
}

//
// P_CrossSubsector
// Returns true
//  if strace crosses the given subsector successfully.
//
boolean P_CrossSubsector (int num)
{
    seg_t*      seg;
    line_t*     line;
    int         s1;
    int         s2;
    int         count;
    subsector_t*    sub;
    sector_t*       front;
    sector_t*       back;
    fixed_t     opentop;
    fixed_t     openbottom;
    divline_t       divl;
    vertex_t*       v1;
    vertex_t*       v2;
    fixed_t     frac;
    fixed_t     slope;

#ifdef RANGECHECK
    if (num>=numsubsectors)
    I_Error ("P_CrossSubsector: ss %i with numss = %i",
         num,
         numsubsectors);
#endif

    sub = &subsectors[num];

    // check lines
    count = sub->numlines;
    seg = &segs[sub->firstline];

    for ( ; count ; seg++, count--)
    {
    line = seg->linedef;

    // allready checked other side?
    if (line->validcount == validcount)
        continue;

    line->validcount = validcount;

    v1 = line->v1;
    v2 = line->v2;
    s1 = P_DivlineSide (v1->x,v1->y, &strace);
    s2 = P_DivlineSide (v2->x, v2->y, &strace);

    // line isn't crossed?
    if (s1 == s2)
        continue;

    divl.x = v1->x;
    divl.y = v1->y;
    divl.dx = v2->x - v1->x;
    divl.dy = v2->y - v1->y;
    s1 = P_DivlineSide (strace.x, strace.y, &divl);
    s2 = P_DivlineSide (t2x, t2y, &divl);

    // line isn't crossed?
    if (s1 == s2)
        continue;

        // Backsector may be NULL if this is an "impassible
        // glass" hack line.

        if (line->backsector == NULL)
        {
            return false;
        }

    // stop because it is not two sided anyway
    // might do this after updating validcount?
    if ( !(line->flags & ML_TWOSIDED) )
        return false;

    // crosses a two sided line
    front = seg->frontsector;
    back = seg->backsector;

    // no wall to block sight with?
    if (front->floorheight == back->floorheight
        && front->ceilingheight == back->ceilingheight)
        continue;

    // possible occluder
    // because of ceiling height differences
    if (front->ceilingheight < back->ceilingheight)
        opentop = front->ceilingheight;
    else
        opentop = back->ceilingheight;

    // because of ceiling height differences
    if (front->floorheight > back->floorheight)
        openbottom = front->floorheight;
    else
        openbottom = back->floorheight;

    // quick test for totally closed doors
    if (openbottom >= opentop)
        return false;       // stop

    frac = P_InterceptVector2 (&strace, &divl);

    if (front->floorheight != back->floorheight)
    {
        slope = FixedDiv (openbottom - sightzstart , frac);
        if (slope > bottomslope)
        bottomslope = slope;
    }

    if (front->ceilingheight != back->ceilingheight)
    {
        slope = FixedDiv (opentop - sightzstart , frac);
        if (slope < topslope)
        topslope = slope;
    }

    if (topslope <= bottomslope)
        return false;       // stop
    }
    // passed the subsector ok
    return true;
}



//
// P_CrossBSPNode
// Returns true
//  if strace crosses the given node successfully.
//
boolean P_CrossBSPNode (int bspnum)
{
    node_t* bsp;
    int     side;

    if (bspnum & NF_SUBSECTOR)
    {
    if (bspnum == -1)
        return P_CrossSubsector (0);
    else
        return P_CrossSubsector (bspnum&(~NF_SUBSECTOR));
    }

    bsp = &nodes[bspnum];

    // decide which side the start point is on
    side = P_DivlineSide (strace.x, strace.y, (divline_t *)bsp);
    if (side == 2)
    side = 0;   // an "on" should cross both sides

    // cross the starting side
    if (!P_CrossBSPNode (bsp->children[side]) )
    return false;

    // the partition plane is crossed here
    if (side == P_DivlineSide (t2x, t2y,(divline_t *)bsp))
    {
    // the line doesn't touch the other side
    return true;
    }

    // cross the ending side
    return P_CrossBSPNode (bsp->children[side^1]);
}


//
// P_CheckSight
// Returns true
//  if a straight line between t1 and t2 is unobstructed.
// Uses REJECT.
//
boolean
P_CheckSight
( mobj_t*   t1,
  mobj_t*   t2 )
{
    int     s1;
    int     s2;
    int     pnum;
    int     bytenum;
    int     bitnum;

    // First check for trivial rejection.

    // Determine subsector entries in REJECT table.
    s1 = (t1->subsector->sector - sectors);
    s2 = (t2->subsector->sector - sectors);
    pnum = s1*numsectors + s2;
    bytenum = pnum>>3;
    bitnum = 1 << (pnum&7);

    // Check in REJECT table.
    if (rejectmatrix[bytenum]&bitnum)
    {
    sightcounts[0]++;

    // can't possibly be connected
    return false;
    }

    // An unobstructed LOS is possible.
    // Now look from eyes of t1 to any part of t2.
    sightcounts[1]++;

    validcount++;

    sightzstart = t1->z + t1->height - (t1->height>>2);
    topslope = (t2->z+t2->height) - sightzstart;
    bottomslope = (t2->z) - sightzstart;

    strace.x = t1->x;
    strace.y = t1->y;
    t2x = t2->x;
    t2y = t2->y;
    strace.dx = t2->x - t1->x;
    strace.dy = t2->y - t1->y;

    // the head node is the last node output
    return P_CrossBSPNode (numnodes-1);
}


